A relationship that often arises between components of a software system is the producer/consumer pattern. In such a pattern, a group of one or more producers need to communicate messages or other data to a group of one or more consumers. For convenience, the consumed items are referred to herein generally as “messages,” but may include objects, data structures, strings, and/or any other data that a producer can communicate to a consumer.
Communication between producers and consumers is sometimes implemented using an intermediary data structure. The intermediary might expose an insert( ) function that producers can invoke to insert new messages and a consume( ) function that consumers can invoke to retrieve and remove an inserted message from the intermediary. Thus, the intermediary effectively decouples the production and consumption activities by enabling a producer to insert a message into the structure and a consumer to independently retrieve that message later. The intermediary guarantees that inserted items are not consumed more than once.
Different types of intermediaries can make different ordering guarantees. For example, a FIFO queue implementation guarantees that items are consumed in the same order as they are inserted. Different types of queues may make different ordering guarantees (e.g., a LIFO queue, priority queue, etc.). A bag is an intermediary that makes no ordering guarantee.
A blocking intermediary blocks a consumer that attempts to consume an item when the intermediary is empty. Thus, the intermediary may make one or more consumers wait if the intermediary is empty. When a producer finally does insert an item into the bag, the intermediary returns the item to one of the blocked consumers, thereby releasing that consumer.
A concurrent intermediary is a thread-safe intermediary, that is, one that maintains correctness, even if multiple producers and/or consumers are executing in parallel. For example, a concurrent bag guarantees that, when multiple consumers and producers attempt to access the bag concurrently, each inserted message is still never consumed more than once. Concurrent systems, in which different threads concurrently perform the production and consumption activities, require concurrent intermediaries.
To make an intermediary concurrent (i.e., thread-safe), previous designs would use a mutual-exclusion lock to control concurrent access to the intermediary. In such implementations, a producer or consumer must first obtain and hold an exclusive lock on the intermediary before performing the put or take operation.
It is often inefficient to control access to an intermediary using an exclusive lock. First, the lock creates a point of contention as the concurrent threads attempt to obtain it concurrently. Second, while a producer or consumer holds the lock, other threads cannot access the intermediary at all. Accordingly, there has been much interest in designing more efficient concurrent data structures.